package com.wengu.recursion;

import org.junit.jupiter.api.Test;

/**
 * 走迷宫问题
 * <p>
 * 创建二维数组，某节点的值为0代表没有走过的路，1代表墙，2代表走过的路，3代表死路
 *
 * @Author whl
 * @Date 2021/6/30 18:17
 * @Version 1.0
 */
public class MazeDemo {
    int column = 9;
    int row = 8;


    @Test
    public void test() {

        int[][] arr = new int[row][column];
        this.maze(arr);
    }

    public void maze(int[][] arr) {
        for (int i = 0; i < column; i++) {
            arr[0][i] = 1;
            arr[row - 1][i] = 1;
        }
        for (int i = 0; i < row; i++) {
            arr[i][0] = 1;
            arr[i][column - 1] = 1;
        }
        arr[4][1] = 1;
        arr[4][2] = 1;

        System.out.println("==========迷宫地图==========");
        // 打印迷宫
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }

        // 走迷宫策略
        step(arr, 1, 1);
        System.out.println("==========走迷宫的路线==========");
        // 打印走迷宫路线
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 策略1
     * 左、下、右、上
     *
     * @param arr
     * @param i
     * @param j
     * @return
     */
    private boolean step(int[][] arr, int i, int j) {
        if (arr[row - 2][column - 2] == 2) {
            return true;
        }
        if (arr[i][j] == 0) {
            // 假设该路能走通
            arr[i][j] = 2;
            if (step(arr, i, j-1)) {
                return true;
            } else if (step(arr,i+1,j)){
                return true;
            } else if (step(arr,i,j+1)){
                return true;
            } else if (step(arr,i-1,j)){
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

}
